// https://leetcode.cn/problems/find-the-duplicate-number/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 快慢指针法寻找重复数（Floyd判圈算法）
// 2. 第一阶段：快指针走两步，慢指针走一步，找到相遇点
// 3. 第二阶段：两指针分别从头和相遇点出发，单步前进
// 4. 再次相遇点即为重复数（环入口）
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int findDuplicate(vector<int>& nums) 
    {
        int m = nums.size();

        int slow = nums[0], fast = nums[0];
        do
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);

        slow = nums[0];
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

int main()
{
    vector<int> nums1 = {1,3,4,2,2}, nums2 = {3,1,3,4,2};
    Solution sol;

    cout << sol.findDuplicate(nums1) << endl;
    cout << sol.findDuplicate(nums2) << endl;

    return 0;
}